#pragma once
#include <iostream>
#include <cassert>
#include <string>

namespace ns_BinSeaTree
{
    template <class K, class V>
    struct BSTreeNode
    {
    public:
        std::pair<K, V> _kv;
        BSTreeNode<K, V> *_left;
        BSTreeNode<K, V> *_right;

        BSTreeNode(const std::pair<K, V> &kv) : _kv(kv), _left(nullptr), _right(nullptr)
        {
        }
    };

    template <class K, class V>
    class BSTree
    {
    public:
        typedef BSTreeNode<K, V> Node;

        BSTree() : _root(nullptr)
        {}

        Node *find(const K &key)
        {
            Node *cur = _root;
            while (cur)
            {
                if (cur->_kv.first == key)
                    return cur;
                else if (cur->_kv.first > key)
                    cur = cur->_left;
                else
                    cur = cur->_right;
            }

            return nullptr;
        }

        bool insert(const K &key, const V &value)
        {
            if (find(key)) // 节点已经存在
                return false;
            Node *newnode = new Node(std::make_pair(key, value));
            if (_root == nullptr)
            {
                _root = newnode;
                return true;
            }

            Node *cur = _root;
            Node *pre = nullptr;
            while (cur)
            {
                pre = cur;
                if (cur->_kv.first > key)
                    cur = cur->_left;
                else
                    cur = cur->_right;
            }
            if (pre->_kv.first > key)
                pre->_left = newnode;
            else
                pre->_right = newnode;

            return true;
        }

        bool erase(const K &key)
        {
            assert(_root != nullptr);
            if (find(key) == nullptr)
                return false;
            Node *cur = _root;
            Node *pre = nullptr;
            while (cur)
            {
                if (cur->_kv.first == key)
                {
                    break;
                }
                else if (cur->_kv.first > key)
                {
                    pre = cur;
                    cur = cur->_left;
                }
                else
                {
                    pre = cur;
                    cur = cur->_right;
                }
            }
            // 要删除的节点为叶子节点
            if (cur->_left == nullptr)
            {
                if (pre == nullptr)
                {
                    _root = cur->_right;
                }
                else
                {
                    if (pre->_left == cur)
                        pre->_left = cur->_right;
                    else
                        pre->_right = cur->_right;
                }
                delete cur;
            }
            else if (cur->_right == nullptr)
            {
                if (pre == nullptr)
                {
                    _root = cur->_left;
                }
                else
                {
                    if (pre->_right == cur)
                        pre->_right = cur->_left;
                    else
                        pre->_left = cur->_left;
                }
                delete cur;
            }
            else
            {
                Node *Min = cur->_right;
                Node *Minpre = cur;
                while (Min->_left)
                {
                    Minpre = Min;
                    Min = Min->_left;
                }
                cur->_val = Min->_val;
                if (Minpre->_left == Min)
                    Minpre->_left = Min->_right;
                else
                    Minpre->_right = Min->_right;
                delete Min;
            }

            return true;
        }

        void Inorder()
        {
            _Inorder(_root);
            std::cout << std::endl;
        }

    private:
        void _Inorder(Node *&root)
        {
            if (nullptr == root)
                return;
            _Inorder(root->_left);
            std::cout << root->_kv.first << ":" << root->_kv.second << " ";
            _Inorder(root->_right);
        }

    private:
        Node *_root;
    };

    void TestBSTree()
    {
        // BSTree<std::string, std::string> dict;
        // dict.insert("insert", "插入");
        // dict.insert("erase", "删除");
        // dict.insert("left", "左边");
        // dict.insert("string", "字符串");

        // std::string str;
        // while (std::cin >> str)
        // {
        //     auto ret = dict.find(str);
        //     if (ret)
        //     {
        //         std::cout << str << ":" << ret->_kv.second << std::endl;
        //     }
        //     else
        //     {
        //         std::cout << "单词拼写错误" << std::endl;
        //     }
        // }

        std::string strs[] = {"苹果", "西瓜", "苹果", "樱桃", "苹果", "樱桃", "苹果", "樱桃", "苹果"};
        // 统计水果出现的次数
        BSTree<std::string, int> countTree;
        for (auto str : strs)
        {
            auto ret = countTree.find(str);
            if (ret == nullptr)
            {
                countTree.insert(str, 1);
            }
            else
            {
                ret->_kv.second++;
            }
        }
        countTree.Inorder();
    }
}